Erdős conjecture on arithmetic progressions

Erdős' conjecture on arithmetic progressions, often incorrectly referred to as the Erdős–Turán conjecture (see also Erdős–Turán conjecture on additive bases), is a conjecture in additive combinatorics due to Paul Erdős. It states that if the sum of the reciprocals of the members of a set A of positive integers diverges, then A contains arbitrarily long arithmetic progressions.

Formally, if

\sum_{n\in A} \frac{1}{n} = \infty

(i.e. A is a large set) then A contains arithmetic progressions of any given length.

If true, the theorem would generalize Szemerédi's theorem.

Erdős offered a prize of US$3000 for a proof of this conjecture at the time.[1] The problem is currently worth US$5000.[2]

The Green–Tao theorem on arithmetic progressions in the primes is a special case of this conjecture.

Notes

  1. ^ Bollobás, Béla (March 1988). "To Prove and Conjecture: Paul Erdős and His Mathematics". American Mathematical Monthly 105 (3): 233. 
  2. ^ p. 354, Soifer, Alexander (2008); The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of its Creators; New York: Springer. ISBN 978-0387746401

References